{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Dot Product of Two Sparse Vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #design #array #hash-table #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #设计 #数组 #哈希表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dotProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个稀疏向量的点积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个稀疏向量，计算它们的点积（数量积）。</p>\n",
    "\n",
    "<p>实现类 <code>SparseVector</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>SparseVector(nums)</code> 以向量 <code>nums</code> 初始化对象。</li>\n",
    "\t<li><code>dotProduct(vec)</code> 计算此向量与 <code>vec</code> 的点积。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>稀疏向量</strong> 是指绝大多数分量为 0 的向量。你需要 <strong>高效</strong> 地存储这个向量，并计算两个稀疏向量的点积。</p>\n",
    "\n",
    "<p><strong>进阶：</strong>当其中只有一个向量是稀疏向量时，你该如何解决此问题？</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>v1 = SparseVector(nums1) , v2 = SparseVector(nums2)\n",
    "v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>v1 = SparseVector(nums1) , v2 = SparseVector(nums2)\n",
    "v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 <= n <= 10^5</code></li>\n",
    "\t<li><code>0 <= nums1[i], nums2[i] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [dot-product-of-two-sparse-vectors](https://leetcode.cn/problems/dot-product-of-two-sparse-vectors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [dot-product-of-two-sparse-vectors](https://leetcode.cn/problems/dot-product-of-two-sparse-vectors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,2,3]\\n[0,3,0,4,0]', '[0,1,0,0,0]\\n[0,0,0,0,2]', '[0,1,0,0,2,0,0]\\n[1,0,0,0,3,0,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.memo = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n!=0:\n",
    "                self.memo[i] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for i, n in self.memo.items():\n",
    "            if i in vec.memo:\n",
    "                res += n*vec.memo[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.value = []\n",
    "        for i, v in enumerate(nums):\n",
    "            if v:\n",
    "                self.value.append((i, v)) \n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        i=j=0\n",
    "        l1 = len(self.value)\n",
    "        l2 = len(vec.value)\n",
    "        ans = 0\n",
    "        while(i<l1 and j<l2):\n",
    "            if self.value[i][0] == vec.value[j][0]:\n",
    "                ans += self.value[i][1] * vec.value[j][1]\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif self.value[i][0] < vec.value[j][0]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for i in range(len(self.nums)):\n",
    "            res += self.nums[i] * vec.nums[i]\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.data = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.data[i] = num\n",
    "        \n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        for pos, num in self.data.items():\n",
    "            if pos in vec.data:\n",
    "                result += num * vec.data[pos]\n",
    "        return result\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "        self.validbits = set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                self.validbits.add(i)\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        valid = self.validbits.intersection(vec.validbits)\n",
    "        ans = 0\n",
    "        for i in valid:\n",
    "            ans += self.nums[i] * vec.nums[i]\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.d = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n:\n",
    "                self.d[i] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for k in self.d:\n",
    "            if k in vec.d:\n",
    "                res += self.d[k] * vec.d[k]\n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dict={}\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            if num !=0:\n",
    "                self.dict[i]=num\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res=0\n",
    "        if len(self.dict)>len(vec.dict):\n",
    "            for key,val in vec.dict.items():\n",
    "                if key in self.dict:\n",
    "                    res+=(self.dict[key]*val)\n",
    "        else:\n",
    "            for key,val in self.dict.items():\n",
    "                if key in vec.dict:\n",
    "                    res+=(vec.dict[key]*val)\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = {}\n",
    "        for i, v in enumerate(nums):\n",
    "            if v:\n",
    "                self.dic[i] = v \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        productSum = 0\n",
    "        for idx, value in vec.dic.items():\n",
    "            if idx in self.dic:\n",
    "                productSum += value * self.dic[idx]\n",
    "        \n",
    "        return productSum\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nonzero_dict = {}\n",
    "        for ind, val in enumerate(nums):\n",
    "            if val != 0:\n",
    "                self.nonzero_dict[ind] = val \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for key, val in self.nonzero_dict.items():\n",
    "            if key in vec.nonzero_dict:\n",
    "                res += val * vec.nonzero_dict[key]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nonzeros = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.nonzeros[i] = n              \n",
    "\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        # 迭代这个稀疏向量中的每个非零元素\n",
    "        # 如果对应的索引在另一个向量中具有非零值，则更新点积\n",
    "        for i, n in self.nonzeros.items():\n",
    "            if i in vec.nonzeros:\n",
    "                result += n * vec.nonzeros[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.denseVec={}\n",
    "        for i,x in enumerate(nums):\n",
    "            if x!=0:\n",
    "                self.denseVec[i]=x\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res=0\n",
    "        for key,val in self.denseVec.items():\n",
    "            if key not in vec.denseVec:\n",
    "                continue\n",
    "            res+=val*vec.denseVec[key]\n",
    "        \n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.nums[i] = num\n",
    "\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        total = 0\n",
    "        for key in self.nums:\n",
    "            if key in vec.nums:\n",
    "                total += self.nums[key] * vec.nums[key]\n",
    "        return total\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums):\n",
    "        self.array = nums\n",
    "\n",
    "    def dotProduct(self, vec):\n",
    "        result = 0\n",
    "        for num1, num2 in zip(self.array, vec.array):\n",
    "            result += num1 * num2\n",
    "        return result\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.index_to_num = {i:nums[i] for i in range(len(nums)) if nums[i] != 0}\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        common = set(self.index_to_num.keys()).intersection(set(vec.index_to_num.keys()))\n",
    "        return sum(self.index_to_num[i] * vec.index_to_num[i] for i in common)\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        return sum([self.nums[i]*vec.nums[i] for i in range(len(self.nums))])\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        return sum([self.nums[i]*vec.nums[i] for i in range(len(self.nums))])\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = dict()\n",
    "        for k, v in enumerate(nums):\n",
    "            if v != 0:\n",
    "                self.dic[k] = v\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for k, v in self.dic.items():\n",
    "            if k in vec.dic:\n",
    "                res += v * vec.dic[k]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vec = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.vec[i] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for i, n in self.vec.items():\n",
    "            if i in vec.vec:\n",
    "                res += n * vec.vec[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nonzeros = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.nonzeros[i] = n      \n",
    "\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        for i, n in self.nonzeros.items():\n",
    "            if i in vec.nonzeros:\n",
    "                result += n * vec.nonzeros[i]\n",
    "        return result\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.index_to_num = defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                self.index_to_num[i] = nums[i]\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        return sum(num * vec.index_to_num[i] for i, num in self.index_to_num.items())\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.dic[i] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ret = 0\n",
    "        for pos in self.dic:\n",
    "            if pos in vec.dic:\n",
    "                ret += self.dic[pos] * vec.dic[pos]\n",
    "        return ret\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nonzero_dict = {}\n",
    "        for ind, val in enumerate(nums):\n",
    "            if val != 0:\n",
    "                self.nonzero_dict[ind] = val \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for key, val in self.nonzero_dict.items():\n",
    "            if key in vec.nonzero_dict:\n",
    "                res += val * vec.nonzero_dict[key]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nonzeros = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.nonzeros[i] = n      \n",
    "\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        for i, n in self.nonzeros.items():\n",
    "            if i in vec.nonzeros:\n",
    "                result += n * vec.nonzeros[i]\n",
    "        return result\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vec = {}\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.vec[idx] = num\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0\n",
    "        for key, num in self.vec.items():\n",
    "            if key not in vec.vec:\n",
    "                continue\n",
    "            ans += num * vec.vec[key]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.sparse_idx = []\n",
    "        self.sparse_val = []\n",
    "        for i, val in enumerate(nums):\n",
    "            if val != 0:\n",
    "                self.sparse_idx.append(i)\n",
    "                self.sparse_val.append(val)\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ptr_one = 0\n",
    "        ptr_two = 0\n",
    "        out = 0\n",
    "        while ptr_one < len(self.sparse_idx) and ptr_two < len(vec.sparse_idx):\n",
    "            if self.sparse_idx[ptr_one] == vec.sparse_idx[ptr_two]:\n",
    "                out += (self.sparse_val[ptr_one] * vec.sparse_val[ptr_two])\n",
    "                ptr_one += 1\n",
    "                ptr_two += 1\n",
    "            elif self.sparse_idx[ptr_one] < vec.sparse_idx[ptr_two]:\n",
    "                ptr_one += 1\n",
    "            else:\n",
    "                ptr_two += 1\n",
    "        return out\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = collections.defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                self.dic[i] = nums[i]\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for k, v in self.dic.items():\n",
    "            if k in vec.dic:\n",
    "                res += v * vec.dic[k]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vec_d = {idx: val for idx, val in enumerate(nums) if val != 0}\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        n, m = len(self.vec_d), len(vec.vec_d)\n",
    "        v1, v2 = self.vec_d, vec.vec_d\n",
    "        if n > m:\n",
    "            v1, v2 = v2, v1\n",
    "        res = 0\n",
    "        for k in v1.keys():\n",
    "            if k in v2:\n",
    "                res += v1[k] * v2[k]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.index_dict = {}\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num:\n",
    "                self.index_dict[idx] = num\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for key in self.index_dict.keys():\n",
    "            if key in vec.index_dict:\n",
    "                res += self.index_dict[key] * vec.index_dict[key]\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vt = {k:v for k,v in enumerate(nums) if v} # 取非零下标\n",
    "        \n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        com = set(i for i in self.vt).intersection(j for j in vec.vt) # 取非零交集下标\n",
    "        return sum(self.vt[c]*vec.vt[c] for c in com)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.i_t_v = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.i_t_v[i] = num\n",
    "\n",
    "    def get_size(self):\n",
    "        return len(self.i_t_v)\n",
    "\n",
    "    def has_index(self, i):\n",
    "        return i in self.i_t_v\n",
    "\n",
    "    def get_index(self, i):\n",
    "        if self.has_index(i):\n",
    "            return self.i_t_v[i]\n",
    "\n",
    "        raise RuntimeError(\"index {} not valid\".format(i))\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        s1 = self.get_size()\n",
    "        s2 = vec.get_size()\n",
    "        t = 0\n",
    "        if s1 < s2:\n",
    "            for k, v in self.i_t_v.items():\n",
    "                if vec.has_index(k):\n",
    "                    t += v * vec.get_index(k)\n",
    "        else:\n",
    "            for k, v in vec.i_t_v.items():\n",
    "                if self.has_index(k):\n",
    "                    t += v * self.get_index(k)\n",
    "\n",
    "        return t\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class SparseVector:\n",
    "#     def __init__(self, nums: List[int]):\n",
    "#         self.dic = collections.defaultdict(int)\n",
    "#         for i, num in enumerate(nums):\n",
    "#             self.dic[i] = num \n",
    "\n",
    "#     # Return the dotProduct of two sparse vectors\n",
    "#     def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "#         res = 0\n",
    "#         for i, num in vec.dic.items():\n",
    "#             if i in self.dic:\n",
    "#                 res += num * self.dic[i]\n",
    "#         return res\n",
    "        \n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.nums.append([i, num])\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        v1, v2 = self.nums, vec.nums\n",
    "        while i < len(v1) and j < len(v2):\n",
    "            if v1[i][0] == v2[j][0]:\n",
    "                res += v1[i][1] * v2[j][1]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif v1[i][0] < v2[j][0]:\n",
    "                i = bisect.bisect_left(v1, [v2[j][0], 0])\n",
    "            else:\n",
    "                j = bisect.bisect_left(v2, [v1[i][0], 0])\n",
    "        return res\n",
    "        \n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class SparseVector:\n",
    "#     def __init__(self, nums: List[int]):\n",
    "#         self.dic = collections.defaultdict(int)\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num != 0:\n",
    "#                 self.dic[i] = num\n",
    " \n",
    "#     # Return the dotProduct of two sparse vectors\n",
    "#     def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "#         res = 0\n",
    "#         for k, v in vec.dic.items():\n",
    "#             if k in self.dic:\n",
    "#                 res += v* self.dic[k]\n",
    "#         return res\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.nums.append((i, num)) # append()\n",
    "        \n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        while i < len(self.nums) and j < len(vec.nums):\n",
    "            num1, num2 = self.nums[i], vec.nums[j]\n",
    "            if num1[0] == num2[0]:\n",
    "                res += num1[1] * num2[1]\n",
    "                i += 1 # super important!!!!! i +=1 j += 1\n",
    "                j += 1\n",
    "            elif num1[0] < num2[0]:\n",
    "                i = self.bs(self.nums, (num2[0], 0))\n",
    "                # i = bisect.bisect_left(self.nums, (num2[0], 0))\n",
    "            else:\n",
    "                j = self.bs(vec.nums, (num1[0], 0))\n",
    "                # j = bisect.bisect_left(vec.nums, (num1[0], 0))\n",
    "        return res\n",
    "\n",
    "    def bs(self, nums, target):\n",
    "        n = len(nums)\n",
    "        start, end = 0, n -1\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if nums[mid] >= target:\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid\n",
    "        if nums[start] >= target:\n",
    "            return start\n",
    "        elif nums[end] >= target:\n",
    "            return end\n",
    "        else:\n",
    "            return n\n",
    "                       \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.array = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        for nums1, nums2 in zip(self.array, vec.array):\n",
    "            result += nums1 * nums2\n",
    "        return result\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        return sum(x*y for x,y  in zip(self.nums, vec.nums))\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vals = {i: num for i, num in enumerate(nums) if num != 0}\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        keys = [i for i in self.vals.keys() if i in vec.vals.keys()]\n",
    "        return sum([vec.vals[i] * self.vals[i] for i in keys])\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums=nums\n",
    "        self.non_zero=set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]:\n",
    "                self.non_zero.add(i)\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        non_zero=self.non_zero.union(vec.non_zero)\n",
    "        res=0\n",
    "        for i in non_zero:\n",
    "            res+=self.nums[i]*vec.nums[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = collections.defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.dic[i] = num\n",
    " \n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for k, v in vec.dic.items():\n",
    "            if k in self.dic:\n",
    "                res += v* self.dic[k]\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums=nums\n",
    "        self.non_zero=set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]:\n",
    "                self.non_zero.add(i)\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        non_zero=self.non_zero.union(vec.non_zero)\n",
    "        res=0\n",
    "        for i in non_zero:\n",
    "            res+=self.nums[i]*vec.nums[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.v = dict()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v != 0:\n",
    "                self.v[i] = v\n",
    "        # self.len = len(nums)\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        if len(self.v) < len(vec.v):\n",
    "            pass\n",
    "        else:\n",
    "            self.v, vec.v = vec.v, self.v\n",
    "        ans = 0\n",
    "        for i in self.v:\n",
    "            if i not in vec.v:\n",
    "                continue\n",
    "            else:\n",
    "                ans += self.v[i] * vec.v[i]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.array = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        result = 0\n",
    "        for num1, num2 in zip(self.array, vec.array):\n",
    "            result += num1 * num2\n",
    "        return result\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        \n",
    "        self.A = set()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.A.add((i, num))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for (i, val1) in self.A:\n",
    "            for (j, val2) in vec.A:\n",
    "                if i == j:\n",
    "                    res += val1*val2\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for i in range(len(self.nums)):\n",
    "            res += self.nums[i]*vec.nums[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.sv = dict()\n",
    "        for idx, n in enumerate(nums):\n",
    "            if n!=0:\n",
    "                self.sv[idx] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        set1 = set(vec.sv.keys())\n",
    "        set2 = set(self.sv.keys())\n",
    "        comm_set = set1.intersection(set2)\n",
    "        ans = 0\n",
    "        for k in comm_set:\n",
    "            ans += vec.sv[k] * self.sv[k]\n",
    "        return ans\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class SparseVector:\n",
    "#     def __init__(self, nums: List[int]):\n",
    "#         self.dic = collections.defaultdict(int)\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num != 0:\n",
    "#                 self.dic[i] = num\n",
    " \n",
    "#     # Return the dotProduct of two sparse vectors\n",
    "#     def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "#         res = 0\n",
    "#         for k, v in vec.dic.items():\n",
    "#             if k in self.dic:\n",
    "#                 res += v* self.dic[k]\n",
    "#         return res\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.nums.append((i, num)) # append()\n",
    "        \n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        while i < len(self.nums) and j < len(vec.nums):\n",
    "            num1, num2 = self.nums[i], vec.nums[j]\n",
    "            if num1[0] == num2[0]:\n",
    "                res += num1[1] * num2[1]\n",
    "                i += 1 # super important!!!!! i +=1 j += 1\n",
    "                j += 1\n",
    "            elif num1[0] < num2[0]:\n",
    "                i = self.bs(self.nums, (num2[0], 0))\n",
    "                # i = bisect.bisect_left(self.nums, (num2[0], 0))\n",
    "            else:\n",
    "                j = self.bs(vec.nums, (num1[0], 0))\n",
    "                # j = bisect.bisect_left(vec.nums, (num1[0], 0))\n",
    "        return res\n",
    "\n",
    "    def bs(self, nums, target):\n",
    "        n = len(nums)\n",
    "        start, end = 0, n -1\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if nums[mid] >= target:\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid\n",
    "        if nums[start] >= target:\n",
    "            return start\n",
    "        elif nums[end] >= target:\n",
    "            return end\n",
    "        else:\n",
    "            return n\n",
    "                       \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums_hashmap = {}\n",
    "        self.vec_len = len(nums)\n",
    "\n",
    "        for idx, n in enumerate((nums)):\n",
    "            if n != 0:\n",
    "                self.nums_hashmap[idx] = n        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "\n",
    "        for idx in self.nums_hashmap.keys():\n",
    "            if vec.nums_hashmap.get(idx, 0) != 0:\n",
    "                res += self.nums_hashmap[idx] * vec.nums_hashmap[idx]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.record = collections.defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.record[i] = num\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        for key in self.record:\n",
    "            if key in vec.record:\n",
    "                res += self.record[key] * vec.record[key]\n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums_hashmap = {}\n",
    "        self.vec_len = len(nums)\n",
    "\n",
    "        for idx, n in enumerate((nums)):\n",
    "            if n != 0:\n",
    "                self.nums_hashmap[idx] = n        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "\n",
    "        for i in range(self.vec_len):\n",
    "            if self.nums_hashmap.get(i, 0) != 0 and vec.nums_hashmap.get(i, 0) != 0:\n",
    "                res += self.nums_hashmap[i] * vec.nums_hashmap[i]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.v = dict()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v != 0:\n",
    "                self.v[i] = v\n",
    "        self.len = len(nums)\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0\n",
    "        for i in range(self.len):\n",
    "            if i not in self.v or i not in vec.v:\n",
    "                continue\n",
    "            else:\n",
    "                ans += self.v[i] * vec.v[i]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.datas = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.datas[i] = num\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        len1, len2 = len(self.datas), len(vec.datas)\n",
    "        if len1 < len2:\n",
    "            a, b = self.datas, vec.datas\n",
    "        else:\n",
    "            a, b = vec.datas, self.datas\n",
    "        result = 0\n",
    "        for k in a:\n",
    "            if k in b:\n",
    "                result += a[k] * b[k]\n",
    "        return result\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def convert_sparse_vector(self, nums: List) -> List:\n",
    "        sparse_list = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                sparse_list.append((i, nums[i]))\n",
    "        return sparse_list\n",
    "\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.sparse_vector = self.convert_sparse_vector(nums)\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        vec1 = self.sparse_vector\n",
    "        vec2 = vec.sparse_vector\n",
    "\n",
    "        res = 0\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        while i < len(vec1) and j < len(vec2):\n",
    "            if vec1[i][0] == vec2[j][0]:\n",
    "                res += vec1[i][1]* vec2[j][1]\n",
    "                i += 1\n",
    "                j += 1\n",
    "                \n",
    "            elif vec1[i][0] < vec2[j][0]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vector = dict()\n",
    "        for i, n in enumerate(nums):\n",
    "            if n != 0:\n",
    "                self.vector[i] = n\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        product = 0\n",
    "        for i in self.vector.keys():\n",
    "            if i in vec.vector.keys():\n",
    "                product += self.vector[i] * vec.vector[i]\n",
    "        return product\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = {i:v for i,v in enumerate(nums) if v!=0}\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        p = vec.dic\n",
    "        for i in p:\n",
    "            if i in self.dic:\n",
    "                res += p[i]*self.dic[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.idx_val = [(idx, val) for idx, val in enumerate(nums) if val != 0]\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        l1, l2 = self.idx_val, vec.idx_val \n",
    "        if len(l1) > len(l2):\n",
    "            l1, l2 = l2, l1\n",
    "        idx2 = 0\n",
    "        res = 0\n",
    "        for idx1, val1 in l1:\n",
    "            idx2 = self.binarySearch(l2, idx1, 0, len(l2)-1)\n",
    "            if idx2 != -1:\n",
    "                res += val1 * l2[idx2][1]\n",
    "        return res\n",
    "\n",
    "    def binarySearch(self, nums, target, left, right):\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid][0] == target:\n",
    "                return mid \n",
    "            elif nums[mid][0] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.list = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num:\n",
    "                self.list.append((i, num))\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        if len(vec.list) > len(self.list):\n",
    "            return vec.dotProduct(self)\n",
    "        res = 0\n",
    "        for i, num in vec.list:\n",
    "            res += num * self.binary_search(i, 0, len(self.list) - 1)\n",
    "        return res\n",
    "\n",
    "    def binary_search(self, i, l, r):\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if self.list[mid][0] == i:\n",
    "                return self.list[mid][1]\n",
    "            elif self.list[mid][0] < i:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return 0\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.v = []\n",
    "        self.nums = nums[:]\n",
    "        for i,x in enumerate(nums):\n",
    "            if x!=0:\n",
    "                self.v.append((i,x))\n",
    "        return \n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0 \n",
    "        for i,x in self.v:\n",
    "            ans += vec.nums[i]*x\n",
    "        return ans \n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        # self.vec = {}\n",
    "        # for i, n in enumerate(nums):\n",
    "        #     if n != 0:\n",
    "        #         self.vec[i] = n\n",
    "        self.none_zeros = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.none_zeros.append((i, num))\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        # res = 0\n",
    "        # for i, n in self.vec.items():\n",
    "        #     if i in vec.vec:\n",
    "        #         res += n * vec.vec[i]\n",
    "        # return res\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        while i < len(self.none_zeros) and j < len(vec.none_zeros):\n",
    "            if self.none_zeros[i][0] == vec.none_zeros[j][0]:\n",
    "                res += self.none_zeros[i][1] * vec.none_zeros[j][1]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif self.none_zeros[i][0] < vec.none_zeros[j][0]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.v = []\n",
    "        \n",
    "        for i,x in enumerate(nums):\n",
    "            if x!=0:\n",
    "                self.v.append((i,x))\n",
    "        return \n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0 \n",
    "        p,q = 0,0 \n",
    "        n,m = len(self.v), len(vec.v)\n",
    "        while p<n and q<m:\n",
    "            x,y = self.v[p], vec.v[q]\n",
    "            if x[0]==y[0]:\n",
    "                ans += x[1]*y[1]\n",
    "                p += 1\n",
    "                q += 1\n",
    "            elif x[0]>y[0]:\n",
    "                q += 1\n",
    "            else:\n",
    "                p += 1\n",
    "        return ans \n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.vec = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num != 0:\n",
    "                self.vec.append((idx, num))\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        while idx1 < len(self.vec) and idx2 < len(vec.vec):\n",
    "            if self.vec[idx1][0] == vec.vec[idx2][0]:\n",
    "                ans += self.vec[idx1][1] * vec.vec[idx2][1]\n",
    "                idx1 += 1\n",
    "                idx2 += 1\n",
    "            elif self.vec[idx1][0] < vec.vec[idx2][0]:\n",
    "                idx1 += 1\n",
    "            else:\n",
    "                idx2 += 1\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.idx_val = [(idx, val) for idx, val in enumerate(nums) if val != 0]\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        l1, l2 = self.idx_val, vec.idx_val \n",
    "        if len(l1) > len(l2):\n",
    "            l1, l2 = l2, l1\n",
    "        idx2 = 0\n",
    "        res = 0\n",
    "        for idx1, val1 in l1:\n",
    "            idx2 = self.binarySearch(l2, idx1, 0, len(l2)-1)\n",
    "            if idx2 != -1:\n",
    "                res += val1 * l2[idx2][1]\n",
    "        return res\n",
    "\n",
    "    def binarySearch(self, nums, target, left, right):\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid][0] == target:\n",
    "                return mid \n",
    "            elif nums[mid][0] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.pair = []\n",
    "        for i, val in enumerate(nums):\n",
    "            if val != 0:\n",
    "                self.pair.append([i, val])\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        ans = 0\n",
    "        i, j = 0, 0\n",
    "        while i < len(self.pair) and j < len(vec.pair):\n",
    "            if self.pair[i][0] == vec.pair[j][0]:\n",
    "                ans += self.pair[i][1] * vec.pair[j][1]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif self.pair[i][0] < vec.pair[j][0]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.memo=[]\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            if num !=0:\n",
    "                self.memo.append([i,num])\n",
    "        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res=0\n",
    "        p=0 \n",
    "        q=0\n",
    "\n",
    "        while p<len(self.memo) and q<len(vec.memo):\n",
    "            if self.memo[p][0]==vec.memo[q][0]:\n",
    "                res+=(self.memo[p][1]*vec.memo[q][1])\n",
    "                p+=1\n",
    "                q+=1\n",
    "            elif self.memo[p][0]>vec.memo[q][0]:\n",
    "                q+=1\n",
    "            else:\n",
    "                p+=1\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, pos=-1, val=-1) -> None:\n",
    "        self.pos = pos\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "    \n",
    "    def __str__(self) -> str:\n",
    "        return f\"pos: {self.pos}, val:{self.val}\"\n",
    "\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.len = len(nums)\n",
    "        self.storage = self.compress(nums)\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.len\n",
    "    \n",
    "    def compress(self, nums):\n",
    "        dummy = Node()\n",
    "        cur = dummy\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                cur.next = Node(i, nums[i])\n",
    "                cur = cur.next\n",
    "        return dummy.next\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = [0 for _ in range(self.len)]\n",
    "        a = vec.storage\n",
    "        b = self.storage\n",
    "        while a and b:\n",
    "            # print(a, b)\n",
    "            if a.pos > b.pos:\n",
    "                b = b.next\n",
    "            elif a.pos < b.pos:\n",
    "                a = a.next\n",
    "            else:\n",
    "                res[a.pos] = a.val * b.val\n",
    "                a = a.next\n",
    "                b = b.next\n",
    "        # print(res)\n",
    "        return sum(res)\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.dic = {i:v for i,v in enumerate(nums)}\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res = 0\n",
    "        p = vec.dic\n",
    "        for i in p:\n",
    "            res += p[i]*self.dic[i]\n",
    "        return res\n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.denseVec={}\n",
    "        for i,x in enumerate(nums):\n",
    "            self.denseVec[i]=x\n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        res=0\n",
    "        for key,val in self.denseVec.items():\n",
    "            if key not in vec.denseVec:\n",
    "                continue\n",
    "            res+=val*vec.denseVec[key]\n",
    "        \n",
    "        return res\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SparseVector:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.d = {}\n",
    "        for i in range(len(nums)):\n",
    "            self.d[i] = nums[i]        \n",
    "\n",
    "    # Return the dotProduct of two sparse vectors\n",
    "    def dotProduct(self, vec: 'SparseVector') -> int:\n",
    "        r = 0\n",
    "        for i in vec.d:\n",
    "            if i in self.d:\n",
    "                r += self.d[i] * vec.d[i]\n",
    "            else:\n",
    "                r += vec.d[i]\n",
    "        return r\n",
    "        \n",
    "\n",
    "# Your SparseVector object will be instantiated and called as such:\n",
    "# v1 = SparseVector(nums1)\n",
    "# v2 = SparseVector(nums2)\n",
    "# ans = v1.dotProduct(v2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
